{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "起点：0\n",
      "    路径：[0, 2, 3, 1, 0]\n",
      "    距离：23\n",
      "起点：1\n",
      "    路径：[1, 3, 0, 2, 1]\n",
      "    距离：26\n",
      "起点：2\n",
      "    路径：[2, 3, 0, 1, 2]\n",
      "    距离：28\n",
      "起点：3\n",
      "    路径：[3, 0, 2, 1, 3]\n",
      "    距离：26\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "adj = np.array([[99, 8, 5, 36],\n",
    "                [6, 99, 8, 5],\n",
    "                [8, 9, 99, 5],\n",
    "                [7, 7, 8, 99]])\n",
    "\n",
    "def tsp(v,adj,start,result):\n",
    "    if len(v)!=0:\n",
    "        result.append(start)\n",
    "        sortIndex = np.argsort(adj[start,v])\n",
    "        id = v[sortIndex[0]]\n",
    "        v.remove(start)\n",
    "        tsp(v,\n",
    "            adj,\n",
    "            id,\n",
    "            result\n",
    "        )\n",
    "\n",
    "for i in range(len(adj)):\n",
    "    v = [0,1,2,3]\n",
    "    result=[]\n",
    "    tsp(v,adj,i,result)\n",
    "    result.append(result[0])\n",
    "    print(\"起点：{}\".format(i))\n",
    "    print(\"    路径：{}\".format(result))\n",
    "    print(\"    距离：{}\".format(sum([adj[result[i],result[i+1]] for i in range(len(result)-1)])))\n",
    "    "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.9.12 ('base')",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.12"
  },
  "vscode": {
   "interpreter": {
    "hash": "bfb6b6056bbcee18ee270338479bcc9a7798e633b623cdbb3c7849c1f8787a17"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
